1. Field of the Invention
The present invention relates to a method and an apparatus for parallel computation and, more particularly, to a method and an apparatus for parallel computation capable of achieving an improved processing efficiency.
2. Description of the Prior Art
In a parallel computer utilizing a network formed by a multiplicity of interconnected processing units, the interconnection in general is furnished in a form of a two-dimensional torus network or N-cube network which connects the neighboring processing units. In such configurations, exchanges of messages between processing units not directly connected are carried out by passing through several processing units lying between such processing units.
FIG. 1 shows an example of such a configuration in which PE represents a processing element, R represents a router which controls transfers of messages in and out of the associated processing element, and a pair of PE and R forms a processing unit.
Messages are exchanged between the processing units in terms of message packets such as one shown in FIG. 2. A message packet consists of a header containing an address of the sending processing element(sender address), an address of the receiving processing element(receiver address), and a length of the message data(data length), and a main portion containing the message data itself(data). The routers control the routes of the message transfer by selecting the best path chosen to avoid the heavily engaged region.
Now, if a parallel computer contained approximately 10 .sup.3 processing units, each of the address of the sending processing element and the address of the receiving processing element requires about 10 bits of memory space, so that at least 20 bits are necessary for the header of the message packet. In such a case, when message data itself is short, most of the message packet transferred consists of the header rather than the message data itself which conveys the actual information needed to be transferred so that the efficiency of message exchange becomes very low. In particular, when it is necessary to transfer a vast amount of short messages such as those of not much more than 1 bite length, the efficiency of message exchange becomes extremely low.